/*
    SDL - Simple DirectMedia Layer
    Copyright (C) 1997, 1998, 1999  Sam Lantinga

    This library is SDL_free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    Sam Lantinga
    slouken@devolution.com
*/

/* The RLE encoding implementation for software colorkey acceleration */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <SDL/SDL.h>
#include <SDL/SDL_types.h>
#include <SDL/SDL_error.h>
#include <SDL/SDL_video.h>
#include "SDL_sysvideo.h"
#include "SDL_blit.h"
#include "SDL_RLEaccel_c.h"

/* Run-length-encoding operations */
#define RLE_DONE	0
#define RLE_COPY	1
#define RLE_SKIP	2
#define RLE_LINE	3

/* Limits on size (so we don't SDL_malloc on clipping) */
#define RLE_MAXX	(640/2)		/* Can be increased */
#define RLE_MAXY	(480/2)		/* Can be increased */
#define RLE_MAXSIZE							\
	RLE_MAXY*1 +			/* RLE_LINE operations */	\
	RLE_MAXY*((RLE_MAXX+1)/2)*5 +	/* Worst case RLE line */	\
	1				/* RLE_DONE */
/* The worst case RLE line is alternating pixel and blank */


/* Macro to eat a RLE buffer until the CONDITION is met */
#define MUNCH_RLE(CONDITION)					\
	while ( CONDITION ) {					\
		op = *srcbuf;					\
		switch (op) {					\
			case RLE_DONE:				\
				goto done;			\
			case RLE_COPY:				\
				srcbuf += (2+*(srcbuf+1));	\
				break;				\
			case RLE_SKIP:				\
				srcbuf += 2;			\
				break;				\
			default:				\
				srcbuf++;			\
				break;				\
		}						\
	}

/* Function to quickly clip a RLE buffer */
static Uint8 *SDL_RLEClip(Uint8 *srcbuf, int bpp, SDL_Rect *cliprect)
{
	static Uint8 rlebuf[RLE_MAXSIZE];
	Uint8 op;
	int i, diff, len = 0;
	int x, y, minx, maxx, maxy;

	i = 0;

	/* Clip the top off */
	for ( y=0; y<cliprect->y; ++y ) {
		op = RLE_DONE;
		MUNCH_RLE((op != RLE_LINE));
	}

	/* Clip left and right, until bottom */
	minx =  cliprect->x*bpp;
	maxx = (cliprect->x+cliprect->w)*bpp;
	maxy = (cliprect->y+cliprect->h);
	while ( y < maxy ) {
		op = RLE_DONE;
		x = 0;
		while ( (op != RLE_LINE) && (x < minx) ) {
			op = *srcbuf;
			switch (op) {
				case RLE_DONE:
					goto done;
				case RLE_COPY:
					x      += *(srcbuf+1);
					srcbuf += (2+*(srcbuf+1));
					break;
				case RLE_SKIP:
					x      += *(srcbuf+1);
					srcbuf += 2;
					break;
				default:
					srcbuf++;
					break;
			}
		}
		if ( x >= minx ) {
			diff = x-minx;
			if ( diff > 0 ) {
				rlebuf[i++] = op;
				rlebuf[i++] = diff;
				if ( op == RLE_COPY ) {
					memcpy(&rlebuf[i], srcbuf-diff, diff);
					i += diff;
				}
			}
			do {
				op = *srcbuf;
				switch (op) {
					case RLE_DONE: {
						goto done;
					}
					case RLE_COPY: {
						x += *(srcbuf+1);
						len = *(srcbuf+1)+2;
						memcpy(&rlebuf[i], srcbuf, len);
						srcbuf += len;
						i += len;
					}
					break;
					case RLE_SKIP: {
						x += *(srcbuf+1);
						len = 2;
						memcpy(&rlebuf[i], srcbuf, len);
						srcbuf += len;
						i += len;
					}
					break;
					default: {
						srcbuf++;
					}
					break;
				}
			} while ( (op != RLE_LINE) && (x <= maxx) );
			/* If x > maxx, 
			   we need to truncate an operation and wait for the
			   original buffer to reach end-of-line or end-of-buf
			 */
			if ( x > maxx ) {
				if ( op == RLE_COPY ) {
					diff = x-maxx;
					rlebuf[i-len+1] -= diff;
					i -= diff;
				} else {
					/* Drop last RLE_SKIP */
					i -= 2;
				}
				MUNCH_RLE((op != RLE_LINE));
			}
		}
		rlebuf[i++] = RLE_LINE;
		++y;
	}
 done:
	rlebuf[i] = RLE_DONE;
	return(rlebuf);
}

/* Function to quickly blit a RLE buffer */
int SDL_RLEBlit(SDL_Surface *src, SDL_Rect *srcrect,
			SDL_Surface *dst, SDL_Rect *dstrect)
{
	Uint8 *dstbuf;
	Uint8 *srcbuf;
	int x, y;

	/* Lock the destination if necessary */
	if ( (dst->flags & SDL_HWSURFACE) == SDL_HWSURFACE ) {
		SDL_VideoDevice *video = current_video;
		SDL_VideoDevice *this  = current_video;
		if ( video->LockHWSurface(this, dst) < 0 ) {
			return(-1);
		}
	}

	/* Set up the source and destination pointers */
	x = dstrect->x;
	y = dstrect->y;
	dstbuf = (Uint8 *)dst->pixels+dst->offset+
				y*dst->pitch+x*dst->format->BytesPerPixel;
	if ( srcrect->x || srcrect->y || 
			(srcrect->w != src->w) || (srcrect->h != src->h) ) {
		srcbuf = SDL_RLEClip((Uint8 *)src->map->sw_data->aux_data, 
					src->format->BytesPerPixel, srcrect);
	} else {
		srcbuf = (Uint8 *)src->map->sw_data->aux_data;
	}

	/* Do it! */
	while ( *srcbuf != RLE_DONE ) {
		switch (*srcbuf) {
			case RLE_DONE: {
			}
			break;
			case RLE_COPY: {
				Uint8 len;

				++srcbuf;
				len = *srcbuf;
				++srcbuf;
#ifdef DEBUG_RLEBLIT
{ int z; for ( z=0; z<len/src->format->BytesPerPixel; ++z ) printf("X"); }
#endif
				memcpy(dstbuf, srcbuf, len);
				srcbuf += len;
				dstbuf += len;
			}
			break;
			case RLE_SKIP: {
				++srcbuf;
#ifdef DEBUG_RLEBLIT
{ int z; for ( z=0; z<*srcbuf/src->format->BytesPerPixel; ++z ) printf("_"); }
#endif
				dstbuf += *srcbuf;
				++srcbuf;
			}
			break;
			case RLE_LINE: {
				++y;
#ifdef DEBUG_RLEBLIT
printf("\n");
#endif
				dstbuf = (Uint8 *)dst->pixels + dst->offset +
						y*dst->pitch +
						x*dst->format->BytesPerPixel;
				++srcbuf;
			}
			break;
			default: {
				++srcbuf;	/* Corrupted RLE buffer? */
			}
			break;
		}
	}
#ifdef DEBUG_RLEBLIT
fflush(stdout);
#endif

	/* Unlock the destination if necessary */
	if ( (dst->flags & SDL_HWSURFACE) == SDL_HWSURFACE ) {
		SDL_VideoDevice *video = current_video;
		SDL_VideoDevice *this  = current_video;
		video->UnlockHWSurface(this, dst);
	}
	return(0);
}

static int Transparent(Uint8 *srcbuf, SDL_PixelFormat *fmt)
{
	switch (fmt->BytesPerPixel) {
		case 1:
			return( *srcbuf == (Uint8)fmt->colorkey);
		case 2:
			return(*((Uint16 *)srcbuf) == (Uint16)fmt->colorkey);
		case 3: {
			Uint8 r, g, b;
			Uint32 pixel;

			r = *((srcbuf)+fmt->Rshift/8);
			g = *((srcbuf)+fmt->Gshift/8);
			b = *((srcbuf)+fmt->Bshift/8);
			pixel = ((r>>fmt->Rloss)<<fmt->Rshift)|
				((g>>fmt->Gloss)<<fmt->Gshift)|
				((b>>fmt->Bloss)<<fmt->Bshift);
			return(pixel == fmt->colorkey);
		}
		case 4:
			return(*((Uint32 *)srcbuf) == fmt->colorkey);
		default:
			return(0);	/* ?? */
	}
}
#undef FLUSH_RLE
#define FLUSH_RLE()	{					\
	n *= bpp;						\
	if ( n > 0 ) {						\
		rleops[o++] = op;				\
		rlebuf[i++] = op;				\
		rlebuf[i++] = n;				\
		if ( op == RLE_COPY ) {				\
			memcpy(&rlebuf[i], srcbuf, n);		\
			i += n;					\
		}						\
		srcbuf = curbuf;				\
		n = 0;						\
	}							\
}

int SDL_RLESurface(SDL_Surface *surface)
{
	Uint8 *rlebuf;
	Uint8 *rleops;
	int i, o, n, maxn;
	int x, y, bpp, trim;
	Uint8 *srcbuf, *curbuf, op;

	/* Clear any previous RLE conversion */
	if ( (surface->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
		SDL_UnRLESurface(surface);
	}

	/* We don't support alpha blending on RLE surfaces */
	if ( (surface->flags & SDL_SRCALPHA) == SDL_SRCALPHA ) {
		return(-1);
	}

	/* We also don't support RLE encoding of bitmaps */
	if ( surface->format->BitsPerPixel < 8 ) {
		return(-1);
	}

	/* Make sure the surface is small enough to be encoded */
	if ( (surface->w > RLE_MAXX) || (surface->h > RLE_MAXY) ) {
		return(-1);
	}

	/* Lock the surface if it's in hardware */
	if ( (surface->flags & SDL_HWSURFACE) == SDL_HWSURFACE ) {
		SDL_VideoDevice *video = current_video;
		SDL_VideoDevice *this  = current_video;
		if ( video->LockHWSurface(this, surface) < 0 ) {
			return(-1);
		}
	}

	/* Metrowerks compiler can't handle really big local arrays */
	rlebuf = (Uint8 *)SDL_malloc(RLE_MAXSIZE);
	if ( rlebuf == NULL ) {
		SDL_OutOfMemory();
		return(-1);
	}
	rleops = (Uint8 *)SDL_malloc(RLE_MAXSIZE/2);
	if ( rleops == NULL ) {
		SDL_free(rlebuf);
		SDL_OutOfMemory();
		return(-1);
	}

	/* Set up the conversion */
	srcbuf = (Uint8 *)surface->pixels+surface->offset;
	curbuf = srcbuf;
	bpp = surface->format->BytesPerPixel;
	trim = surface->pitch - surface->w*bpp;
	op = RLE_LINE;
	i = 0;
	o = 0;
	n = 0;
	maxn = (255/bpp);
	for ( y=0; y<surface->h; ++y ) {
		for ( x=0; x<surface->w; ++x ) {
			if ( n == maxn ) {
				FLUSH_RLE();
			}
			if ( Transparent(curbuf, surface->format) ) {
				switch (op) {
					case RLE_SKIP:
						break;
					case RLE_COPY:
						FLUSH_RLE();
					default:
						op = RLE_SKIP;
						break;
				}
				++n;
			} else {
				switch (op) {
					case RLE_COPY:
						break;
					case RLE_SKIP:
						FLUSH_RLE();
					default:
						op = RLE_COPY;
						break;
				}
				++n;
			}
			curbuf += bpp;
		}
		FLUSH_RLE();
		/* Optimize away trailing space */
		while ( (o > 0) && (rleops[o-1] == RLE_SKIP) ) {
			i -= 2;
			--o;
		}
		rleops[o++] = RLE_LINE;
		rlebuf[i++] = RLE_LINE;
		curbuf += trim;
		srcbuf += trim;
	}
	/* Optimize away trailing lines */
	while ( (o > 0) && (rleops[o-1] == RLE_LINE) ) {
		--i;
		--o;
	}
	rlebuf[i++] = RLE_DONE;

	/* Unlock the surface if it's in hardware */
	if ( (surface->flags & SDL_HWSURFACE) == SDL_HWSURFACE ) {
		SDL_VideoDevice *video = current_video;
		SDL_VideoDevice *this  = current_video;
		video->UnlockHWSurface(this, surface);
	}

	/* Copy the RLE buffer to the surface */
	SDL_free(rleops);
	surface->map->sw_data->aux_data = SDL_malloc(i);
	if ( surface->map->sw_data->aux_data == NULL ) {
		SDL_free(rlebuf);
		SDL_OutOfMemory();
		return(-1);
	}
	memcpy(surface->map->sw_data->aux_data, rlebuf, i);
	SDL_free(rlebuf);

	/* The surface is now accelerated */
	surface->flags |= SDL_RLEACCEL;
	return(0);
}

void SDL_UnRLESurface(SDL_Surface *surface)
{
	if ( (surface->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
		if ( surface->map->sw_data->aux_data ) {
			SDL_free(surface->map->sw_data->aux_data);
			surface->map->sw_data->aux_data = NULL;
		}
		surface->flags &= ~SDL_RLEACCEL;
	}
}

